The invention relates generally to the field of electronic design automation (EDA), and particularly to a system and method for improving the speed and accuracy of latch inference in EDA.
Discrete function simulation is one of the core tasks in rapid system prototyping and debugging in EDA. Improvements in discrete function simulation time can dramatically improve system design time. Discrete function simulators address the problem of finding the values of circuit outputs, given a circuit design and a vector of circuit input values. One example of a discrete function simulator is a logic simulator.
Until recently, conventional logic simulators in the EDA environment operated in an event-driven manner, wherein a plurality of wires connect a plurality of logic elements within a circuit-under-test. As input vectors cascade through the logic elements the logical value (1 or 0) of each wire may change. Each change in the value of a wire is regarded as an event. A memory queue stores the events. When the logical value of a wire changes, each gate having the modified wire as an input is subsequently tested to determine whether the logical value on the output wire of the gate has changed. A change in the value on this output wire is a new event which is placed in the memory queue. This process continues until all of the gates within the circuit-under-test have been processed.
The performance of such conventional logic simulators is therefore dependent upon the number of gates in the simulated circuit and is limited by the size and speed of the memory queue. Hundreds of thousands or even millions of gates may be present on a single integrated circuit (IC), e.g., an application specific integrated circuit (ASIC) or circuit implemented on a programmable or reprogrammable logic device. Simulating all of the gates and events occurring on such an IC requires a significant amount of time and computer resources.
To address the need for a more efficient logic simulator which functions in a manner independent of the number of gates in a circuit and the number of events occurring in a system, McGeer, et al. invented and patented an event-independent SYSTEM AND METHOD FOR SIMULATING DISCRETE FUNCTIONS USING ORDERED DECISION ARRAYS, disclosed and claimed in U.S. Pat. No. 5,752,000 (which is incorporated herein by reference), filed Aug. 2, 1994, issued May 12, 1998, and owned by Cadence Design Systems, Inc., the assignee of the present invention.
The reader will benefit at this point in the background discussion from a brief history of logic design. When the now-ubiquitous hardware design tools Verilog and VHDL were first introduced, no single logic synthesis methodology was in widespread use and the only common verification technology was event-driven simulation. Since that time, however, logic synthesis (the automated optimization of a digital circuit for die area, speed, or power) has become a ubiquitous tool among digital designers. Further, a welter of modern verification tools have been added to the circuit designer""s desktop: timing analysis (which determines the speed of a digital circuit); formal verification (in which the correctness of the design is proven mathematically); and more efficient forms of simulation (xe2x80x9ccyclexe2x80x9d simulation) in which only a small proportion of the actual assignments of the circuit are performed, and thus much greater speed is gained.
All of these latter-day tools operate not on the HDL description of the circuit, but on the circuit itself. However, for a variety of reasons, Verilog and VHDL continue to dictate the input format to all circuit verification tools including synthesis tools (which optimize circuit structure for size, complexity, speed, or consumed power), timing analysis tools (which determine how long a circuit takes to perform its function), and formal verification tools (which formally and completely prove circuit properties). The need, therefore, to rapidly, efficiently, and accurately divine the underlying circuit from an HDL description of a circuit becomes paramount.
Unfortunately, HDLs have their basic semantics strongly rooted in their event-driven simulation origins. In particular, in event-driven simulation, each variable is tied to a memory location: each assignment to the variable is stored in the memory location, and remains the value of the variable until the variable is freshly assigned. In the underlying circuit, this specific behavior can only be realized by attaching a memory circuit to each variablexe2x80x94known in the art to which the present invention pertains as a xe2x80x9clatchxe2x80x9d. However, such latches are both expensive in circuit area and introduce a one-cycle delay to each assignment. For this reason, only about 5-10% of variables in a typical circuit are latched in this manner.
The major problem in finding the underlying circuit from a description in an HDL file is to determine which small set of the variables in the HDL file should be so xe2x80x9clatchedxe2x80x9d. The method must be fast and efficient in all cases, since circuits are often very large, and embody a rule so simple and easy to understand that a competent circuit designer can easily determine which variables in his program will be latched in the realized circuit. This last element is particularly crucial: determination of which signals in a circuit are latched is of great importance in circuit design, and thus must be controlled by the designer.
Thus, while event-independent simulation (often referred to in the industry as fast function evaluation or cycle simulation) has proven advantages, the change has brought severe complications. A cycle simulator cannot seamlessly replace event-driven simulators intended for use with behavioral languages such as Verilog and VHDL. The semantics of event-driven simulation languages find their foundation in the event queue, and so removal of the queue makes simulation difficult. Thus, cycle simulators are based upon a precisely defined, cycle simulating HDL, which comprises a set of state variables and combinational logic. In cycle simulating HDL, combinational logic re-evaluates its output in zero time (clock-independent) in response to an input change, and therefore functions in a manner independent of an event queue.
Put simply, latch inference is the process of determining whether a given design variable is sequential (necessitating a latch-type memory bit) or combinational (no memory needed).
One available approach, provided in the Design Compiler(copyright) software tool sold by Synopsis, Inc., comprises tautology checking, wherein every possible value of a given variable is analyzed, and when any unassigned circumstance is encountered, a latch or more complex sequential element is assigned. However, this tautological method involves a global analysis of the whole design, an exhaustive computation which consumes considerable and costly computational resources, making it impractical for a designer to precisely determine which signals are latched. This system is described and claimed in U.S. Pat. No. 5,530,841 to Gregory, et al., incorporated herein by reference. Thus, Gregory, et. al attach a logic expression to each assignment of a variable, and then determine whether the disjunction of these logic expressions is tautologous. It is therefore assumed in the Gregory approach that fewer latches are better, i.e., that the challenge is one of simple optimization with a simple objective function. This approach is flawed in both the simplicity of its conception and complexity of its execution.
Since tautology checking is an exhaustive and computationally intensive process (i.e., NP-complete), there remains a need in the art for a more refined yet thorough approach to latch inference. More particularly, a fundamental problem in latch inference is determining whether or not a variable is always directly assigned. If it is, then it is assumed that the variable has no need of storage, since its value is determined independent of any stored value. If not, then it is assumed that the stored value is desired where the variable is not directly assigned.
Once the basic challenge is established, the derived problem is that a specific variable is often assigned in different branches of a program: the problems becomes determining whether the program in execution always traverses at least one of the branches under which a specific variable is assigned, or whether there are cases when the program doesn""t traverse such a branch.
The present invention provides a method and apparatus to meet this need in the art without compromising function or efficiency. Data-flow analysis is utilized to provide an efficient means of determining the variables assigned in each program branch. In this analysis, the individual statements in a program are simplified to a data-flow equation in four variables:
out[S]=in[S]+(gen[S]xe2x88x92kill[S])
where out[S] comprises the variables unassigned after statement S is executed, in[S] comprises the variables unassigned before statement S is executed, gen[S] comprises the new variables assigned in statement S, and kill[S] comprises the variables assigned in all branches of statement S. Thus, in[S] and gen[S] are easily defined, while kill[S] is a statement type-specific function, with a different equation for each statement type in a language. For example, given the if statement xe2x80x9cS: if (cond) S1; else Sxe2x80x9d, then kill[S] comprises the intersection of kill[S1] and kill[S2].
Put more precisely, to address the shortcomings of the prior art, the present invention provides a system and method for inferring latch elements in a circuit design from a hardware description language (HDL) file using data flow analysis, the method comprising the steps of identifying and recording a set of variables Lp used in the expression, for a variable within the set Lp, conducting an uninitialized variable analysis for a given input signal, and if the variable is accessed while uninitialized, inferring a latch for that variable.
In one aspect, the method further comprises, if an uninitialized variable is not accessed, inferring a wire.
In another aspect, the method further comprises determining conditions under which the variable is modified, and from the determined conditions inferring a clocking signal for the inferred latch.
In still another aspect, the method of the present invention comprises modeling an HDL file as a plurality of data flow equations, analyzing the plurality of equations for a uninitialized variable, and placing a latch at an uninitialized variable.
In yet another aspect, the method of the present invention further comprises analyzing the plurality of equations for a utilized, uninitialized variable.
In still another aspect, the method of the present invention comprises analyzing an HDL file for variables, for each variable, performing an uninitialized variable analysis, and for each uninitialized variable accessed inferring a latch having a selected control signal.
It is therefore a first advantage of the present invention to provide a latch inference system for circuit simulation and synthesis which utilizes data flow analysis.
It is a second advantage of the present invention to provide a latch inference system for circuit simulation and synthesis which utilizes uninitialized variable analysis.
A system for implementing the method embodiments of the present invention is also disclosed and claimed herein.